package binbaum;

public class SuchBaum implements IBinBaum{
  protected Knoten hohlkopf;

  public SuchBaum(){
    hohlkopf=new Knoten(Integer.MIN_VALUE);
  }

  protected Knoten vaterVon(int wert){
    Knoten vater=hohlkopf;
    Knoten lauf=hohlkopf.rson;
    while(lauf!=null && lauf.datum!=wert){
      vater=lauf;
      if(wert<lauf.datum) lauf=lauf.lson;
      else lauf=lauf.rson;
    }
    return vater;
  }

  @Override
  public boolean insert(int wert){
    Knoten vater=vaterVon(wert);
    if(wert<vater.datum){
      if(vater.lson!=null) return false;
      vater.lson=new Knoten(wert);
    } else{
      if(vater.rson!=null) return false;
      vater.rson=new Knoten(wert);
    }
    return true;
  }

  @Override
  public boolean contains(int wert){
    Knoten vater=vaterVon(wert);
    Knoten sohn= wert<vater.datum? vater.lson : vater.rson;
    return sohn!=null && sohn.datum==wert;
  }

  @Override
  public boolean delete(int wert){
    Knoten vater=vaterVon(wert);
    Knoten sohn= wert<vater.datum? vater.lson : vater.rson;
    if(sohn==null) return false;// nichts zu löschen da
    if(sohn.lson!=null && sohn.rson!=null){
      Knoten bleib=vater=sohn;
      sohn=sohn.rson;// ein Schritt nach rechts...
      while(sohn.lson!=null){//... dann möglichst nach links
        vater=sohn;
        sohn=sohn.lson;
      }
      bleib.datum=wert=sohn.datum;
    }
    sohn= sohn.lson==null? sohn.rson : sohn.lson;
    if(wert<vater.datum) vater.lson=sohn;
    else vater.rson=sohn;
    return true;
  }

  // Die folgende Inner-Class stellt die nötigen Knoten zur Verfügung.
  //============================================================================
  public class Knoten implements IBinKnoten{
    int datum;
    Knoten lson;//linker  Nachfolger
    Knoten rson;//rechter Nachfolger

    public Knoten(int wert){ datum=wert; }
    // Die folgenden Methoden sind nötig für die Zusammenarbeit mit Wrapper.
    @Override
    public IBinKnoten lson(){ return lson; }

    @Override
    public IBinKnoten rson(){ return rson; }

    @Override
    public int datum(){ return datum; }
  }
}
